package DataStructure.dp;

import java.util.ArrayList;
import java.util.List;

//动态规划,即在多属性的限制下选择若干物品,求某个属性的最优解
//重叠子问题:要求解的不同子问题存在重复计算
//最优子结构:原问题的最优解是从子问题的最优解构建得来的
//无后效性:当前状态确定之后,它的未来状态只与当前状态有关,而与过去所有状态无关
public class DP {
    private static int lim=10;//单个属性限制
    private static int n=10;
    private static int[][] arr=new int[n][];//物品属性(cost,val,...)
    private static int[][] mem=new int[n][lim+1];//存储体,一个单元就是一个状态,一个维度就是一个限制


    public static void main(String[] args) {
//        //初始化未存储状态
//        for (int[] ints : mem) {
//            Arrays.fill(ints, -1);
//        }
//
//        dfs01Bag(0,lim);
//
//        //查询达到最低要求需要的最小限制
//        for (int i = 0; i < lim + 1; i++) {
//            if(mem[n-1][i]>5){
//                System.out.println(i);
//            }
//        }


    }

    //递归DP,考虑"选择[idx,end]的物品"的方案的最优解
    public static int dfs01Bag(int idx,int res){
        //边界条件
        if(idx==n) return 0;
        //查询存储
        if(mem[idx][res]!=-1)
            return mem[idx][res];
        //不选的状态变化
        //计算不选择的结果
        int nsl=dfs01Bag(idx+1,res);
        //满足条件则选择
        int sl=0;
        if(res-arr[idx][0]>=0){
            //选择的状态变化
            //计算选择的结果
            sl=dfs01Bag(idx+1,res-arr[idx][0])+arr[idx][1];
        }
        //存储结果
        return mem[idx][res]=Math.max(nsl,sl);
    }
    //递推DP(优化空间)
    public static int rcs01Bag(){
        int[] mem=new int[lim+1];//初始边界条件为0
        //考虑"选择[idx,end]的物品"的方案
        for (int idx = n-1; idx >= 0; idx--) {
            //递推"限制为res"的结果
            for (int res = lim; res >= 0; res--) {
                //计算不选择结果
                int nsl=mem[res];
                //满足条件则选择(在未选择该物品的基础上)
                int sl=0;
                if(res-arr[idx][0]>=0){
                    //计算选择结果
                    sl=mem[res-arr[idx][0]]+arr[idx][1];
                }
                mem[res]=Math.max(nsl,sl);
            }
        }
        return mem[lim];
    }
    //完全背包
    public static int allBag(){
        int[] mem=new int[lim+1];//初始边界条件为0
        //考虑"选择[idx,end]的物品"的方案的最优解
        for (int idx = n-1; idx >= 0; idx--) {
            //递推"限制为res"的结果
            for (int res = 0; res <= lim; res++) {
                //计算不选择结果
                int nsl=mem[res];
                //满足条件则选择(在已选择该物品的基础上)
                int sl=0;
                if(res-arr[idx][0]>=0){
                    //计算选择结果
                    sl=mem[res-arr[idx][0]]+arr[idx][1];
                }
                mem[res]=Math.max(nsl,sl);
            }
        }
        return mem[lim];
    }
    //多重背包(二进制优化)
    public static int mulBag(){
        //"选择[1,n]的若干个数"与"选择[1,2,4...]的若干个数的和"一致
        List<int[]> arr=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a=DP.arr[i][0];//cost
            int b=DP.arr[i][1];//val
            int c=DP.arr[i][2];//num
            //将1,2,4...个物品合并到一个物品
            for (int j = 1;j<=c;c-=j,j<<=1) {
                arr.add(new int[]{j*a,j*b});
            }
            if(c>0) arr.add(new int[]{c*a,c*b});//合并剩余物品
        }
        //01背包
        int[] mem=new int[lim+1];
        for (int idx = arr.size()-1; idx >= 0; idx--) {
            for (int res = lim; res >= 0; res--) {
                int nsl=mem[res];
                int sl=0;
                if(res-arr.get(idx)[0]>=0){
                    sl=mem[res-arr.get(idx)[0]]+arr.get(idx)[1];
                }
                mem[res]=Math.max(nsl,sl);
            }
        }
        return mem[lim];
    }
}
